The present invention relates to flash memories and, more particularly, to a method of improving the performance of a flash memory in which multiple sectors of data are stored per page.
Flash devices are electrically erasable and programmable read-only memories (EEPROMs) made of flash-type, floating-gate transistors and are non-volatile memories similar in function and performance to EPROM memories, with an additional function that allows an in-circuit, programmable operation to erase portions of the memory. Flash devices have the advantage of being relatively inexpensive and requiring relatively little power as compared to traditional magnetic storage disks. However, flash devices have certain limitations that make using them at the physical address level a bit of a problem. In a flash device, it is not practical to rewrite a previously written area of the memory without a prior erase of the area, i.e. flash cells must be erased (e.g. programmed to “one”) before they can be programmed again. Erasing can only be done for relatively large groups of cells usually called “erase blocks” (typically of size 16 to 256 Kbytes in current commercial NAND devices, and of larger size in NOR devices). Therefore updating the contents of a single byte or even of a chunk of 1 kilobytes requires “housekeeping” operations—parts of the erase block that are not updated must first be moved elsewhere so they will be preserved during erasing, and then moved back into place.
Furthermore, some of the blocks of the device are “bad blocks” that are not reliable so that their use should be avoided. Blocks are declared as “bad blocks” either by the manufacturer when initially testing the device or by application software when detecting the failure of the blocks during use of the device in the field.
To overcome these limitations of the background art, a Flash File System (FFS) was disclosed in U.S. Pat. No. 5,404,485 to Ban, which is assigned to the assignee of the present application and which is hereby incorporated by reference as if fully set forth herein. FFS provides a system of data storage and manipulation on flash devices that allows these devices to emulate magnetic disks. In the existing art, applications or operating systems generally interact with the flash storage subsystem not using physical addresses but rather virtual addresses. There is an intermediary layer between the software application and the physical device that provides a mapping from the virtual addresses into the physical addresses. While the software may view the storage system as having a contiguous defect-free medium that can be read or written randomly with no limitations, the physical addressing scheme has “holes” in its address range (due to the bad blocks, for example), and pieces of data that are adjacent to each other in the virtual address range might be greatly separated in the physical address range. The intermediary layer that does the mapping described above may be a software driver running on the same CPU on which the applications run. Alternatively, the intermediary layer may be embedded within a controller that controls the flash device and serves as the interface point for the main CPU of the host computer when the host computer accesses the storage. This is for example the situation in removable memory cards such as secure digital (SD) cards or multimedia cards (MMC), where the card has an on-board controller running a firmware program that, among other functions, implements the type of mapping described above.
Software or firmware implementations doing such address mappings are typically called “flash management systems” or “flash file systems”. The latter term is a misnomer, as the implementations do not necessarily support “files”, in the sense that files are used in operating systems of personal computers, but rather support block device interfaces similar to those exported by hard disk software drivers. Still, the term is commonly used, and the terms “flash file system” and “flash management system” are used herein interchangeably.
Other prior art systems that implement virtual-to-physical address mapping can be found in U.S. Pat. No. 5,937,425 to Ban and U.S. Pat. No. 6,591,330 to Lasser, both of which are incorporated by reference for all purposes as if fully set forth herein.
In U.S. Pat. No. 5,937,425, which is particularly suitable for NAND-type flash devices, the mapping is done as follows, referring to FIG. 1 (prior art). Physical address space 13 is composed of physical units 111 that are actually the erase blocks i.e. the smallest chunks that can be erased. Each physical unit 111 contains one or more physical pages 113, where a page is the smallest chunk that can be written. A virtual address space 11 is composed of virtual units 121 that have the same size as the physical units. Each virtual unit contains one or more virtual pages 123, having the same size as physical pages 113. When a virtual address is provided by an application, for reading or writing, the virtual unit number to which that address belongs is extracted from the virtual address. There is a mapping that assigns to each virtual unit 121 either one physical unit 111 or a chain of more than one physical unit 111. Then physical page 113 corresponding to requested virtual page 123 within virtual unit 121 is located within the corresponding physical unit(s) 111, using a “local” mapping rule that relates virtual pages 123 to physical pages 113, or using control information stored with physical pages 113.
One of the advantages of the methods disclosed in U.S. Pat. No. 5,937,425 is that as the main mapping is done over units rather than pages, the translation tables are much smaller than they would be otherwise, as there are many fewer units than pages. Another advantage is the write performance improvement that results from being able to assign more than one physical unit 111 to one virtual unit 121.
In order for a flash management system to implement the mapping of virtual to physical addresses, it is necessary to associate and store some control information (also called “overhead data” or “metadata”) with the pages and units of the storage system. Even if the flash management system performs its address mappings using translation tables fully kept in RAM, it would still need to store some control information in non-volatile storage, as otherwise the flash management system would not be able to create and initialize its tables when starting up again after a power-down. Therefore all flash management systems write some control fields into the flash memory in addition to the user data stored within the system.
Because of this, all NAND flash devices are manufactured in advance with extra bytes of storage attached to each page. Typically the amount of extra space provided is 16 bytes per 512 bytes of user data space. This “extra area” (or “spare area”) forms an integral part of the page and both the extra area and user data can be written together in a single write operation. The extra area is used by most NAND-type flash management systems for storing whatever control information they need to keep and then retrieve, either during regular operation or at power-up.
The information fields stored in the extra area can be classified into several categories. A good example for the use of such different categories can be seen in U.S. Pat. No. 6,684,289 to Gonzalez et al. (see for example FIG. 10). Note that Gonzalez et al. actually discloses an atypical flash management system that separates the storage of user data from the storage of some of the control information associated with it, unlike what was explained above. Still, Gonzalez et al. is a good example for understanding the different categories of control fields.
The categories of control fields are:
(a) Fields associated with the specific contents of a page. By that we mean the field's value changes if the user data changes. The best (and usually the only) example of such a field is an Error Correction Code (ECC) field, storing parity bits that support the correction of errors in the data. We refer to such fields herein as “page data fields” or (see the discussion below about sectors) “sector data fields”.
(b) Fields associated with a page, but not with the specific data the page contains. One example for such a field is a flag indicating whether the data in the page were deleted by the user and are no longer valid. Another example is a field identifying a portion of the virtual address to which the page belongs. See for example U.S. Pat. No. 6,678,785 to Lasser, in which the disclosed flash management system associates and stores with each page a field identifying the virtual page number within the virtual unit number to which the page corresponds. We refer to such fields herein as “page fields” or (see the discussion below about sectors) “sector fields”.
(c) Fields associated with a complete unit rather than with a single page. One example of such field is a flag indicating whether the unit is currently in use. Another example is a field providing the virtual unit number to which the unit corresponds. Such fields are referred to herein as “unit fields”.
The page data fields and page fields are required for each page. However, unit fields need not be stored with each page but only once per unit. Typically flash management systems store the unit fields in the first page of a unit, sometimes duplicating them in another page for improving reliability. Therefore the total amount of space required for control information per page is the sum of the amounts required for the page data fields, the page fields and the unit fields. This is so even though in most cases, in all pages except the first page of the unit, at least the part of the extra area corresponding to the unit fields is not used.
The amount of extra area available for control information is limited. Typically for NAND flash devices having pages of 512 bytes each, the extra area is 16 bytes per page. Flash management systems must work within this constraint. A trade-off of design goals is necessary so as not to exceed the available extra area. For example, a system design may allocate 6 bytes for ECC bits, leaving 10 bytes for supporting its management algorithms. Or a different system design may allocate 8 bytes for ECC bits, providing for a higher number of errors that can be corrected and consequently achieving a better system reliability. But in this case only 8 bytes are left for supporting the management algorithms, and this might result in more complex and possibly less efficient management algorithms.
Even though it would thus seem advantageous to have flash devices with a larger extra area, flash manufacturers do not generally follow this path because a larger extra area means a more expensive device. Extra area bits consume silicon area exactly as user data bits do, and therefore the larger the extra area the larger the consumed silicon area. Therefore minimizing extra area is highly desirable.
Consequently for any given flash management system, each one of the following goals are desirable:
(a) Reduce the amount of extra area bytes that need to be provided per page. This goal applies to the design of new flash devices, in which it is possible to deviate from the 16-bytes value currently used.
(b) For existing devices with an extra area of 16 bytes, provide as much space as possible for ECC so as to allow better reliability, without compromising management algorithms complexity and efficiency by supporting all control fields as in the prior art.
(c) For existing devices with a given extra area of 16 bytes, keep the ECC field the same size and provide room for more control fields for management algorithms so as to achieve less complex and more efficient flash management.
One class of flash management systems to which the current invention is especially applicable is the class of systems managing flash devices having pages larger than 512 bytes. Typical file systems and operating systems handle user data in chunks called “sectors” that are 512-bytes long. This is the unit of data exchanged between the file system and the storage system in practically all personal computers, including those employing Microsoft DOS or Windows operating systems. Until quite recently most NAND flash devices had a page size of 512 bytes, so there was a natural matching between user data sectors and flash device pages. A sector of user data that is provided to the flash management system to be stored, is written into a single page together with its related control fields. The flash management system has 16 bytes of extra area available for those control fields, as explained above.
Recently however many flash devices with a page size of 2 Kbytes have been introduced into the market. Such devices are preferred by flash manufacturers for high capacities because the larger pages consume less silicon area for the same number of storage bits, and also because such devices have better read/write performance as a larger number of bytes is read or written in parallel. Flash management systems have been adapted to be able to manage such devices, herein called “large-page devices”. An example of such a flash management system capable of handling large-page devices is disclosed in U.S. Pat. No. 6,760,805 to Lasser, which is incorporated by reference for all purposes as if fully set forth herein.
These prior art flash management systems handle large-page devices by allocating multiple user data sectors to a single flash page. We use as an example large pages that are 2 Kbytes as this size is the most common in commercially available large-page NAND flash devices, but other page sizes are also possible and may also benefit from the methods of the present invention. A page of 2 Kbytes can contain four times 512 bytes, and therefore is assigned to contain four user data sectors. In addition to the user data space, a large page contains an extra area of 64 bytes, 64 being four times the 16 bytes extra area of the small-page devices. This makes each large page have a size of 2112 bytes.
Some terminology clarification is required here. As stated above, in the past, flash memory pages contained 512 bytes of user data, or in other words a single data sector. This caused a one-to-one match between pages and sectors. Therefore, even though strictly speaking fields associated with the user's data should have been called “sector data fields” and “sector fields”, they were called above “page data fields” and “page fields”. When discussing large-page flash memories the one-to-one correspondence between pages and sectors is no longer valid as a page corresponds to multiple sectors. Therefore the sector-based terminology is the more appropriate. However, in order to be consistent with prior art, we retain the page-based terminology. To summarize, in the present disclosure and in the appended claims:
a. the terms “page data field” and “sector data field” are synonyms and mean a field associated with the specific contents of a sector of data;
b. the terms “page field” and “sector field” are synonyms and mean a field associated with a sector, but not with the specific data the sector contains.
Some prior art systems write the four sectors sequentially into their joint page, each sector data adjacent to its control area. This is shown in FIG. 2, in which the location of the four sectors and their control information within the page is illustrated. Area 210 occupies bytes 0 to 511 and contains user data of the first sector. Area 220 occupies bytes 512 to 527 and contains the control information of the first sector. Area 230 occupies bytes 528 to 1039 and contains user data of the second sector. Area 240 occupies bytes 1040 to 1055 and contains the control information of the second sector. Area 250 occupies bytes 1056 to 1567 and contains user data of the third sector. Area 260 occupies bytes 1568 to 1583 and contains the control information of the third sector. Area 270 occupies bytes 1584 to 2095 and contains user data of the fourth sector. Area 280 occupies bytes 2096 to 2111 and contains the control information of the fourth sector.
Other prior art systems do not put a sector and its related control information adjacent to each other, but group the control information of all four sectors of a page together. This is shown in FIG. 3, which is the equivalent of FIG. 2 for the case of all the page's control fields grouped together. Area 210A is the equivalent of area 210 and occupies bytes 0 to 511. Area 230A is the equivalent of area 230 and occupies bytes 512 to 1023. Area 250A is the equivalent of area 250 and occupies bytes 1024 to 1535. Area 270A is the equivalent of area 270 and occupies bytes 1536 to 2047. Area 220A is the equivalent of area 220 and occupies bytes 2048 to 2063. Area 240A is the equivalent of area 240 and occupies bytes 2064 to 2079. Area 260A is the equivalent of area 260 and occupies bytes 2080 to 2095. Area 280A is the equivalent of area 280 and occupies bytes 2096 to 2111.
The datasheet of Toshiba's large-page flash device TC58NVG1S3BFT00 also implies such an arrangement (see page 33 in the datasheet)—even though it does not explicitly address the question of where to locate control information within the page, the way the partial page programming segments are arranged implies this is what the device designers had in mind.
FIG. 4 shows a typical structure of the control fields stored in areas 220, 220A, 240, 240A, 260, 260A, 280 and 280A. Each control area is 16 bytes long and has room for 6 bytes of page data fields (typically ECC), 8 bytes of unit fields and 2 bytes of page fields. It should be noted, however, that not all fields are actually in use in this arrangement. While ECC bytes and page fields' bytes are used for every sector within the page and every page within the unit, unit fields' bytes are not always used. Assuming no redundant copies of unit fields are kept, typically only the first sector of the first page of a unit makes use of its unit fields' space. For all other sectors, these bytes remain unused in prior art flash management systems.
It is mainly for this type of flash management systems that manage large-page devices that the methods of the present invention are applicable.